/**
 *    Copyright (C) 2008, 2009  Victor Smirnov <aist11@gmail.com>
 *
 *    This program is free software; you can redistribute it and/or modify
 *    it under the terms of the GNU General Public License as published by
 *    the Free Software Foundation; either version 3 of the License, or
 *    (at your option) any later version.
 *
 *    This program is distributed in the hope that it will be useful,
 *    but WITHOUT ANY WARRANTY; without even the implied warranty of
 *    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 *    GNU General Public License for more details.
 *
 *    You should have received a copy of the GNU General Public License along
 *    with this program; if not, write to the Free Software Foundation, Inc.,
 *    51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA.
 *
 *    See LICENSE.exceptions in the root folder of this project for possible
 *    exceptions
 *
 */

#ifndef __CUBEFS_CORE_BTREE_ITERATOR_API_H
#define __CUBEFS_CORE_BTREE_ITERATOR_API_H

#include <iostream>

#include <cubefs/api/types.hpp>
#include <cubefs/api/models/logs.hpp>
#include <cubefs/core/container/container.hpp>
#include <cubefs/core/btree/names.hpp>

#define CUBEFS_SOURCE "cubefs/core/btree/iterator/api.hpp:" CUBEFS_AT

namespace cubefs    {
namespace ctr       {

using namespace cubefs::btree;


CUBEFS_ITERATOR_PART_BEGIN(IteratorAPIName)

    typedef typename Base::NodeBase                                             NodeBase;

    bool NextKey() {
        CUBEFS_TRACE(me_, "NextKey");
        if (!me_.IsEof()) {
            if (me_.key_idx() < me_.GetChildrenCount(me_.page()) - 1) {
                me_.key_idx()++;
                return true;
            }
            else {
                bool val = me_.NextLeaf();
                me_.SetEof(!val);
                return val;
            }
        }
        else {
            return false;
        }
    }

    bool NextLeaf() {
        CUBEFS_TRACE(me_, "NextLeaf");
        NodeBase* node = me_.GetNextNode(me_.page());
        if (node != NULL) {
            me_.key_idx() = 0;
            me_.page() = node;
            return true;
        }
        return false;
    }

    bool PrevLeaf() {
        CUBEFS_TRACE(me_, "PrevLeaf");
        NodeBase* node = me_.GetPrevNode(me_.page());
        if (node != NULL) {
            me_.page() = node;
            me_.key_idx() = me_.GetChildrenCount(me_.page()) - 1;
            return true;
        }
        return false;
    }


    NodeBase *GetNextNode(NodeBase* page) {
        if (page->is_root()) {
            return NULL;
        }
        else {
            Int parent_idx = page->parent_idx();
            NodeBase* parent = me_.GetParent(page);
            if (parent == NULL) {
                CUBEFS_ERROR(me_, "GetParent for", page, page->parent_id());
                throw NullPointerException(CUBEFS_SOURCE, "Parent must not be null");
            }
            return me_.__get_next_node(parent, parent_idx, page->level());
        }
    }

    NodeBase *GetPrevNode(NodeBase* page) {
        if (page->is_root()) {
            return NULL;
        }
        else {
            Int parent_idx = page->parent_idx();
            NodeBase* parent = me_.GetParent(page);
            if (parent == NULL) throw NullPointerException(CUBEFS_SOURCE, "Parent must not be null");
            return me_.__get_prev_node(parent, parent_idx, page->level());
        }
    }

    void Init() {}

    bool IsFound() {
        return (!me_.IsEof()) && me_.IsNotEmpty();
    }

private:

    NodeBase *__get_next_node(NodeBase* page, Int &idx1, Int level) {
        if (idx1 < me_.GetChildrenCount(page) - 1) {
            NodeBase *page0 = me_.GetChild(page, idx1 + 1);

            while (page0->level() != level) {
                page0 = me_.GetChild(page0, 0);
            }

            idx1++;
            return page0;
        }
        else {
            if (!page->is_root()) {
                NodeBase *parent = me_.GetParent(page);
                Int idx0 = page->parent_idx();
                return __get_next_node(parent, idx0, level);
            }
        }

        return NULL;
    }

    NodeBase *__get_prev_node(NodeBase* page, Int &idx1, Int level) {
        if (idx1 > 0) {
            NodeBase *page0 = me_.GetChild(page, idx1 - 1);

            while (page0->level() != level) {
                page0 = me_.GetLastChild(page0);
            }

            --idx1;
            return page0;
        }
        else {
            if (!page->is_root()) {
                NodeBase *parent = me_.GetParent(page);
                Int idx0 = page->parent_idx();
                return __get_prev_node(parent, idx0, level);
            }
        }

        return NULL;
    }

CUBEFS_ITERATOR_PART_END

}
}

#undef CUBEFS_SOURCE

#endif //__CUBEFS_CORE_BTREE_ITERATOR_API_H
